
import java.util.Iterator;
import java.util.NoSuchElementException;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 * @author WORKSPOT2
 */
public class Deque<Item> implements Iterable<Item> {

    private Node<Item> first;
    private Node<Item> last;
    private int size = 0;

    public Deque() // construct an empty deque
    {
        first = null;
        last = null;
    }

    public boolean isEmpty() // is the deque empty?
    {
        return size == 0;
    }

    public int size() // return the number of items on the deque
    {
        return size;
    }

    public void addFirst(Item item) // insert the item at the front
    {
        if (item == null) {
            throw new NullPointerException();
        }
        Node newFirst = new Node(item, first);
        first = newFirst;
        if (last == null) {
            last = first;
        }
        size++;
    }

    public void addLast(Item item) // insert the item at the end
    {
        if (item == null) {
            throw new NullPointerException();
        }
        Node newLast = new Node(item, last);
        newLast.next = newLast.next == null ? newLast : newLast.next;
        last = newLast;
        if (first == null) {
            first = last;
        }
        size++;
    }

    public Item removeFirst() // delete and return the item at the front
    {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Node<Item> toReturn = first;
        Node newHead = first.next;
        first = newHead;
        size--;
        return toReturn.item;
    }

    public Item removeLast() // delete and return the item at the end
    {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        Node<Item> toReturn = last;
        Node newLast = last.next;
        last = newLast;
        size--;
        return toReturn.item;
    }

    @Override
    public Iterator<Item> iterator() // return an iterator over items in order from front to end
    {
        return new DequeIterator();
    }

    private class Node<Item> {

        Item item;
        Node<Item> next;

        public Node(Item item, Node<Item> next) {
            this.item = item;
            this.next = next;
        }
    }

    private class DequeIterator implements Iterator<Item> {

        private Node<Item> current;
        private int counter = size;

        public DequeIterator() {
            current = first;
        }

        @Override
        public boolean hasNext() {
            return counter > 0;
        }

        @Override
        public Item next() {
            if (current == null || current.item == null) {
                throw new NoSuchElementException();
            }
            Item toReturn = current.item;
            current = current.next;
            counter--;
            return toReturn;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    public static void main(String[] args) // unit testing
    {
        Deque<String> myDeque = new Deque<String>();
        myDeque.addLast("First");
        myDeque.addLast("Second");
        myDeque.addLast("Third");
        myDeque.addLast("Forth");
        myDeque.addLast("Fifth");
        myDeque.removeLast();
        myDeque.removeLast();
        Iterator<String> iter = myDeque.iterator();
        while (iter.hasNext()) {
            System.out.println(iter.next());
        }
    }
}
